package q947_removeStones;


public class Solution_3 {
    /*
    这里的并查集应用非常简单，即为按照不同的石头进行union stones中是不同石头的坐标
    在双层遍历中 如果发现两个石头已经connected 就跳过
    否则判断两个石头是否为同一行列 然后union两个石头即可 最后就会得到分为不同簇的石头集合
     */
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UF uf = new UF(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (uf.conneted(i, j)) continue;
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) uf.union(i, j);
            }
        }
        return n - uf.count();
    }
    class UF {
        private int count;
        private int[] parent;
        private int[] size;
        public UF(int n) {
            this.count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return ;
            // 平衡性优化
            if (size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
            this.count--;
        }
        public boolean conneted(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
        public int count() {
            return this.count;
        }
        private int find(int x) {
            // 路径压缩
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        /*
        找出并查集中
         */
        public int getMaxConnectSize() {
            int maxSize = 0;
            for (int i = 0; i < parent.length; i++) {
                if (i == parent[i]) {
                    maxSize = Math.max(maxSize, size[i]);
                }
            }
            return maxSize;
        }
    }
}
